package com.kevinkk.monotonicstack;

import java.util.*;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */

public class LargestRectangleInHistogram {
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int length = heights.length;
            // 需要考虑首尾的情况，将首尾各补充一个高度为 0 的元素
            int[] newHeights = new int[length + 2];
            System.arraycopy(heights, 0, newHeights, 1, length);
            Deque<Integer> st = new ArrayDeque<>();
            int res = 0;

            for (int i = 0; i < length + 2; i++) {
                // 找到第一个比之前元素小的元素 newHeights[i]
                while (!st.isEmpty() && newHeights[i] < newHeights[st.peekFirst()]) {
                    // 高就是当前栈顶的元素，它是当前最高的元素
                    int h = newHeights[st.removeFirst()];
                    // 此时栈顶的元素就是第二高的元素
                    if (!st.isEmpty()) {
                        int w = i - st.peekFirst() - 1;
                        res = Math.max(res, h * w);
                    }
                }
                st.addFirst(i);
            }

            return res;
        }
    }
}
